1. Field of the Invention
The invention is directed to computer systems and more particularly to the handling of interrupts in a multi-processor environment.
2. Description of Related Art
Computer systems contain external devices that require the occasional attention of the central processor, such as keyboards, disk and diskette drives, and printers. One method of servicing external devices is to test them frequently to determine which, if any, require attention. This method, usually called polling, wastes considerable time in checking devices that do not need service. A more efficient method is to allow each device to interrupt the CPU whenever it wants. Compared with polling, the interrupt method substantially increases system performance.
An interrupt system can be described as a mechanism that allows the central processing unit to respond to unpredictable events. When an interrupt signal is received, the CPU immediately diverts its attention from the task currently executing, but in a manner that allows the future resumption of this task. The processor then executes a routine that is specific to each particular interrupt. In many microprocessors interrupts may be classified as follows:
1. Internal interrupts are those that originate inside the CPU. For example, the divide by zero interrupt is typically an internal interrupt.
2. External interrupts are those initiated by external hardware. External interrupts are signaled to the CPU on an interrupt request line (INTR) or on a nonmaskable interrupt line (NMI). On many microcomputers the INTR line is driven by an Intel 8259A programmable interrupt controller.
3. Software interrupts are those initiated by an INT or INTO instruction.
An external interrupt is a means whereby a source, external to the processor can asynchronously signal the processor to transfer control immediately to a piece of software that is responsible for servicing the source of the external interrupt. Multiple external interrupt requests are sometimes handled by a priority mechanism which allows the highest priority external interrupt to be recognized by the processor before other lower priority external interrupt requests.
External interrupt serialization allows software to prevent a processor from recognizing external interrupts or to allow the processor to recognize external interrupts. In the prior art, external interrupt serialization techniques were applied to single (uniprocessor) systems. There are two major areas where external interrupt serialization has been employed.
Most internal, external, or software interrupts present to the CPU a specific signature, which is encoded in a byte that follows the interrupt opcode. This signature, sometimes called the interrupt type, serves to identify each interrupt to the CPU. However, interrupts generated by a breakpoint or by the INTO (interrupt on overflow) instruction do not contain a signature byte. Interrupts are presented to a processor over a bus activating one or more interrupt pins of the processor chip.
The Intel.TM. 8259A programmable interrupt controller (PIC) is an integrated circuit designed to manage the external interrupts in a microcomputer system. The 8259A is used in many microcomputers although it is not always configured in the same manner. For example, some microcomputers use a single 8259A chip, while others use two 8259A controllers. Furthermore, the 8259A controllers used can be initialized to be triggered differently.
Some microprocessors have two physical lines to signal interrupts, designated as INTR and NMI. The INTR line (interrupt request) may be driven by an Intel 8259A interrupt controller as shown in FIG. 1. In this type of configuration, all interrupt-driven external devices are connected to the 8259A. The original purpose of an NMI line was to warn the microprocessor of an impending catastrophic event, like an imminent power failure, or of a parity error in memory. But some systems use this line for other purposes; for instance, the NMI line may be attached to the keyboard circuit, and in some systems with a math coprocessor, the NMI line is used to report an error exception.
The 8259A handles interrupts that originate in up to eight external devices by assigning a unique code to each interrupt source. This code, call the interrupt type code, is used by the CPU in locating, in a vector table, the address of the corresponding service routine. Interrupts that originate in the 8295A are maskable; that is, they can be individually enabled and disabled by programming the controller's interrupt mask register. In addition, all external interrupts can be temporarily disabled by clearing the processor's interrupt flag (IF) or by resetting IF, thus reenabling external interrupts. The term nonmaskable interrupt is used to designate all interrupts that do not originate in the 8295A interrupt controller and are not affected by the processor's interrupt flag.
In systems that use a single 8295A chip, all external interrupts are mapped to eight lines, designated as IRQ0 to IRQ7. In systems using two 8295A chips, designated as interrupt controllers 1 and 2 there are a total of 16 interrupt lines, IRQ0 to IRQ15. Since IRQ2 is used to cascade the interrupts from controller number 2, it is not assigned to any specific interrupt.
The hardware protection mechanisms of the Intel.TM. 80X86 family of processors serve to achieve the following functions:
1. System software is isolated from application programs.
2. Tasks execute independently of one another.
3. Segments are used according to their data types.
Protection is implemented by establishing limitations on the use of memory and by restricting the instruction set available to applications. The degree of limitation is determined by a hierarchy of four privilege levels supported by the 80X86. Nevertheless, system programs do not have to enable all privilege levels; for example, the OS/2 operating system uses only three of the four privilege levels available on the processor chip.
______________________________________ Applications level 3 (least privileged) Custom extensions level 2 System services level 1 Kernel level 0 (most privileged) ______________________________________
FIG. 2 illustrates a common software hierarchy which show typical assignments of privilege levels. The privilege level is controlled through three privilege-level indicators:
1. DPL (descriptor privilege level). The value of the DPL is stored in the access rights byte of each descriptor. Its value indicates the privilege level of an entire segment of storage.
2. CPL (current privilege level). The CPL is stored in the current code segment selector. It indicates the privilege level of the task currently executing.
3. RPL (requested privilege level). The RPL is stored in bits of a segment selector. The RPL differs from the CPL in that the CPL refers to a code segment selector, while the RPL can refer to any segment.
The 80X86 processor architecture follows specific rules for granting access to data and code segments. For instance, data access is granted if DPL.gtoreq.CPL--in other words, if the privilege level of the data segment is lower than or equal to the privilege level of the current code segment. Note that the higher the privilege level, the lower the numerical value of DPL, CPL, and RPL. Regarding other code segments, access is granted if CPL=DPL, but more privileged code segments can be accessed via special descriptors called call gates.
The 80X86 processor architecture provides four levels of protection as mentioned above for which an OS may choose to place code and data for the OS itself, device driver, subsystems and applications. These are more commonly referred to as Ring 3, 2, 1 and 0. The lower the ring, the more protection is available. An operating system such as OS/2 chose an architecture that utilizes three of the four protection rings, Ring 3, 2, and 0. Application code and data which need a minimum amount of protection reside at Ring 3. Subsystems code and data that require more protection than Ring 3 reside at Ring 2. The OS kernel and device drivers reside at Ring 0.
There are two classes of input/output I/O instructions distinguished by their OP codes. The first class of I/O instructions performs I/O to devices. The second class of instructions are PAEIS instructions. I/O protection is implemented using a combination of two mechanisms. First, there is an I/O privilege level field in the flags register of the processor which contain one of the four rings 0, 1, 2 or 3. Secondly, an I/O permission bit map in the Task State Segment (TSS) controls access to individual ports in the I/O address space. An I/O permission bit map is not always required. For example, if the I/O privilege level (IOPL) is set to 2 then code segments which execute at protection level 2 can execute both classes of I/O instructions without requiring an I/O permission bit map.
The unit of execution for the 80X86 CPU is called a task. The term thread of execution is sometimes used in a similar context. The microprocessor can execute only one task at a time. The CPU switches tasks as a result of an interrupt or of execution of certain instructions. The 80X86 hardware provides complete isolation between tasks. This isolation is based, among other things, on each task having its own independent address space.
The currently executing task is defined by the contents of the processor registers. This is known as the task or processor state. The task register, which is part of 80X86 CPU, contains a selector to the descriptor of the current task. The task segment descriptor has the same 8-byte structure and format as the other 80X86 segment descriptors.
Some external devices controlled by a microprocessor have a timing requirement in which the programming of some or all steps must take place within a certain time span, otherwise the results required cannot be obtained. If external interrupts are allowed to be recognized by the processor while these steps are executing then the external interrupt service routine could prevent the necessary steps from occurring in a timely fashion and thus the desired results might not be achieved. To prevent any delays of this nature from occurring, software that programs timing sensitive devices can prevent external interrupts from occurring using a Processor Architecture External Interrupt Serialization (PAEIS) facility native to the processor or added on at design time.
The software most frequently implemented for controlling an external device is called a device driver. The device driver typically consists of two sections, a task time section which executes when an external interrupt is not in progress and an interrupt time section which executes when an external interrupt is in progress. There are two considerations that must be taken into account by the device driver.
The first is that some aspects of devices require a strict ordering of steps for their programming. For example, as illustrated in FIG. 3, a single register X on a device may serve as an address register which contains the I/O port address for the subsequent read or write from a data port.
FIG. 3 illustrates the interaction between task processing (left side) and interrupt processing (right side). If at task time the device driver wanted to read from port P1, it would load the address register with P1 (300) the address of data port P1, and then read from data port D. Since the loading of address register and the reading of the data port require multiple instructions there exists a window of opportunity where the task time section could read from the incorrect port.
Consider the following scenario illustrated in FIG. 3: if an external interrupt (310) would occur after the task time section has loaded the address register with P1 and the interrupt time section wanted to read from data port P2 it would then load the address register with P2 and then read from data port P2. When execution returned to the task time section he would then read from the data port specified in the address register (330), but the address register contains P2 instead of P1, so it reads from the incorrect port. To protect against this a PAEIS mechanism would be used to prevent an external interrupt from being recognized by the processor until the data has been read from the data port D.
A second consideration is that typically the task time section will add work items to a queue if the device is currently busy. The interrupt time section will remove elements from the queue upon completion of a previous element. Since both task time and interrupt sections are accessing the same queue, a PAEIS mechanism must be used to guarantee that links for the queue do not get corrupted.
In advanced operating systems (OS) where multiple threads are allowed to execute in a multiprogramming (multi-tasking) environment, one of the functions of the OS is to allocate the processor to the runnable threads. Two primary methods are used for making the decision:
A. An OS will typically use a hardware timer for determining when a thread should share the processor with a similar thread at the same priority (round robin).
B. When an external interrupt occurs, it can signal the completion of an event for which some thread was waiting on. If the thread is higher in priority than the currently executing thread a preemption should occur.
In these environments the programmer must use proper serialization techniques to protect his code/resources because at any given time the OS may decide to give the processor(s) to another runnable thread which may also require execution of the same code path or the use of the same resource. The primary mechanism in the prior art for such serialization is the semaphore. Semaphores are well-known in the art. However, semaphore packages themselves sometime require serialization to prevent from being preempted. Since a semaphore package cannot reuse itself because this could lead to an infinite loop, other serialization mechanisms must be used. One of the serialization mechanisms that can be used by semaphore packages is Processor Architected External Interrupt Serialization (PAEIS). By preventing external interrupts from being recognized by the (single) processor, the semaphore package implicitly disables round robin or preemption. Therefore, any modifications or queries can be done to the semaphore data without anyone else modifying or querying the semaphore.
The use of the PAEIS mechanism provides the necessary functionality required in a uniprocessor environment. However, in a multiprocessor (MP) environment there is no equivalent functionality. As stated before, the existing PAEIS functionality is only applicable to the processor which issued the PAEIS instruction(s) to prevent or allow external interrupts. For example if the thread executing on processor A prevents external interrupts from occurring, processor B could still be allowed to execute the code at the same time that processor A was trying to protect it. Since with PAEIS the software expects only one execution instance through the piece of code in the prevent/allow external interrupts section, unpredictable results may occur when multiple processors are used.